#include<cstdio>
#include<vector>
using namespace std;
const int maxn=1e5;
struct node{
    int area;
    int data;
    int next;
};
int main(){
    //freopen("in.txt","r",stdin);

    int start,N,k;
    scanf("%d %d %d",&start,&N,&k);
    node tmp[maxn];
    int area;
    for(int i=0;i<N;i++){
        scanf("%d",&area);
        scanf("%d %d",&tmp[area].data,&tmp[area].next);
        tmp[area].area=area;
    }
    vector<node> ans;
    while(start!=-1){
        ans.push_back(tmp[start]);
        start=tmp[start].next;
    }
    int sum=ans.size();
    vector<node> res;
    res.resize(sum);
    for(int i=0;i<sum;i++){
        if(i<sum-sum%k){
            res[i]=ans[i/k*k+(k-1)-i%k];
        }
        else{
            res[i]=ans[i/k*k+i%k];
        }
    }
    for(int i=0;i<sum-1;i++){
        printf("%05d %d %05d\n",res[i].area,res[i].data,res[i+1].area);
    }
    printf("%05d %d -1\n",res[sum-1].area,res[sum-1].data);
}
